LoS - 2D 视野、光影相关技术研究及分享
About / 关于
一句话介绍一下这个项目，就是基于 Cocos 引擎的 2D 光线追踪、视野范围计算及渲染相关的东西。
Resources / 资源
Repository / 仓库
SSRLoS-CocosCreator_v1 v1.10
https://gitee.com/supersuraccoon/ssrlos-cocoscreator_v1
SSRLoS-CocosCreator_v2 v2.40
https://gitee.com/supersuraccoon/ssrlos-cocoscreator_v2
SSRLoS-Cocos2d-x v3.17
https://gitee.com/supersuraccoon/ssrlos-cocos2dx
Online Demo / 在线演示
SSRLoS-CocosCreator_v1 Demo
https://gitee.com/supersuraccoon/ssrlos-cocoscreator_v1
SSRLoS-CocosCreator_v2 Demo
http://supersuraccoon.gitee.io/ssrlos-cocoscreator_v2
SSRLoS-Cocos2d-x Demo
http://supersuraccoon.gitee.io/ssrlos-cocos2dx
SSRLoS-Cocos2d-x API Demo
codesandbox.io
基于 Cocos2d-x 版本
https://codesandbox.io/s/ssrlos-demo-visibility-744mo
SSRLoS-Cocos2d-x-Visibility
https://codesandbox.io/s/ssrlos-demo-visibility-744mo
SSRLoS-Cocos2d-x-Shadow
https://codesandbox.io/s/ssrlos-demo-shadow-q44qo
SSRLoS-Cocos2d-x-Modes
https://codesandbox.io/s/ssrlos-demo-modes-yxbgj
SSRLoS-Cocos2d-x-Dirty-Detection
https://codesandbox.io/s/ssrlos-demo-dirty-detection-eft0n
SSRLoS-Cocos2d-x-Light
https://codesandbox.io/s/ssrlos-demo-light-0h9gj
SSRLoS-Cocos2d-x-Mask
https://codesandbox.io/s/ssrlos-demo-mask-gihmn
SSRLoS-Cocos2d-x-Multi-Lights
https://codesandbox.io/s/ssrlos-demo-multi-lights-m2ryx
SSRLoS-Cocos2d-x-Multi-Masks
https://codesandbox.io/s/ssrlos-demo-multi-masks-f68bq
SSRLoS-Cocos2d-x-Output-Render
https://codesandbox.io/s/ssrlos-demo-output-render-nwij2
Native Demo / 原生演示
Creator v2.4.0 纯 js 版本
v0.0.1_LoSCCC2_Web.apk
https://gitee.com/supersuraccoon/ssrlos-cocos2dx/attach_files/490534/download
Creator v1.10 纯 js 版本
v0.0.1_LoSCCC1_Web.apk
https://gitee.com/supersuraccoon/ssrlos-cocos2dx/attach_files/490533/download
Cocos2d-x v3.17 jsbinding 版本
v0.0.1_LoSCC_Native.apk
https://gitee.com/supersuraccoon/ssrlos-cocos2dx/attach_files/490531/download
Cocos2d-x v3.17 纯 js 实现版本，无 jsbinding 实现
v0.0.1_LoSCC_Web.apk
https://gitee.com/supersuraccoon/ssrlos-cocos2dx/attach_files/490530/download
Doc / 文档
API / 文档
https://gitee.com/supersuraccoon/ssrlos-doc
Wiki / 百科
https://gitee.com/supersuraccoon/ssrlos-doc/wikis/pages
Plan / 计划
后续的计划，同时包括了很多 2 的光照，阴影相关的技术文章，有兴趣可以看下。
To Explore / 待探索：
https://gitee.com/supersuraccoon/ssrlos-doc/wikis/pages?sort_id=3006599&doc_id=1008958
这里稍微贴一点：
Algorithm / 算法相关
Triangulation
Umbrella Development Log Beamcasting
http://sadumbrella.blogspot.se/2010/11/beamcasting.html
Walls and Shadows in 2D
https://www.gamedev.net/articles/programming/graphics/walls-and-shadows-in-2d-r2711
三角化算法的实现方式，当然这对于地图和障碍物可能会有一些特殊要求。但是换句话说，只要满足了条件，这样的算法的效率肯定是高于现在算法的，毕竟是 量身定做 的算法。
Bresenham
Raytracing on a grid
http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html
直线光栅化算法的实现方式。
Spatial Hashing / 空间散列
Radial Spatial Hashing for 2D Lighting
http://bitnode.co.uk/radial-spatial-hashing-for-2d-lighting/
基于空间散列实现的光照系统，值得参考。
Better Collineation Culling / 优化共线剔除
Culling的处理中，过滤掉了可能出现的重复的端点，但是对于存在于同一射线上的端点，却是在后期生成射线的步骤中，才过滤掉。这期间经历了生成辅助射线的步骤。
考虑是否可以在Culling的阶段就过滤掉，如:
. 对需要保存的端点，计算斜率，象限
. 用 斜率_象限 的形式作为 key
. 判断待添加的端点，是否有已经存在的 斜率_象限
. 没有，则直接保存
. 有，则进一步计算距离平方，只保存一个距离光源更近的端点
目前暂时没有尝试，因为精度的问题，使用斜率作为 Key，很少的情况才会出现命中的情况，换句话说，这种机制可以剔除的共线情况会很少。
需要寻找更好的剔除共射线的方式是最好的。暂时没有尝试。
Better Sort / 优化排序
Better Hashcode / 优化哈希码
Quadtree / 四叉树
quadtree-js
https://github.com/timohausmann/quadtree-js/
Specific Obstacle Support / 特定障碍物对应
Bretter Intersection / 更好的相交算法
Separating Axis Theorem (SAT) Explanation
http://www.sevenson.com.au/actionscript/sat/
Process / 过程相关
Obstacle Merge / 障碍物合并
Connected Component Labeling
https://en.wikipedia.org/wiki/Connected-component_labeling
Clipper - an open source freeware library
http://www.angusj.com/delphi/clipper.php
Event System / 事件系统
生命周期回调
https://docs.cocos.com/creator/manual/zh/scripting/life-cycle-callbacks.html?h=%E7%94%9F%E5%91%BD
Render / 渲染
SDF Ray-Marching / 有向距离场 光线行进
2D global illumination - Shadertoy
https://www.shadertoy.com/view/3ssXRH
lightsdf - Shadertoy
https://www.shadertoy.com/view/lldcDf
SDF arbitary 2D polygon - Shadertoy
https://www.shadertoy.com/view/WdSGRd
sdf 2D lights and shadows - Shadertoy
https://www.shadertoy.com/view/WlSfRD
2D sdf test - Shadertoy
https://www.shadertoy.com/view/3t23DG
2D Signed Distance Field Basics
https://www.ronja-tutorials.com/2018/11/10/2d-sdf-basics.html
2D 光线追踪渲染 - sardinefish
https://www.sardinefish.com/blog/?pid=302#2D%E5%85%89%E7%85%A7%E6%B8%B2%E6%9F%93%E7%9A%84%E5%AE%9E%E7%8E%B0
Less Triangulate Render / 减少三角化渲染
Better Light Shader / 更好的光照
Better Blend Mode / 更好的混合模式
Shadow / 阴影
2D lights and shadows
https://docs.godotengine.org/en/stable/tutorials/2d/2d_lights_and_shadows.html
Shadow Caster 2D
https://docs.unity3d.com/Packages/com.unity.render-pipelines.universal@7.1/manual/2DShadows.html
Difference Between Penumbra and Umbra
http://www.differencebetween.net/science/difference-between-penumbra-and-umbra/
Normal Map
cocos2d-x dynamic light tutoria
https://www.codeandweb.com/spriteilluminator/tutorials/lighting-demo-cocos2d-x
Shadow Map
2D Pixel Perfect Shadows
https://github.com/mattdesl/lwjgl-basics/wiki/2D-Pixel-Perfect-Shadows
Fast 2D shadows in Unity using 1D shadow mapping
https://www.gamasutra.com/blogs/RobWare/20180226/313491/Fast_2D_shadows_in_Unity_using_1D_shadow_mapping.php
Tutorial 16 : Shadow mapping
http://www.opengl-tutorial.org/intermediate-tutorials/tutorial-16-shadow-mapping/
用于 2D 游戏光照的 ShadowMap 生成
https://zhuanlan.zhihu.com/p/75517907
Light
光照基础
https://learnopengl-cn.readthedocs.io/zh/latest/02%20Lighting/02%20Basic%20Lighting/
Unity 中实现 2D 光照系统
https://zhuanlan.zhihu.com/p/67923713
Glare Engine
http://tizsoft.altervista.org/glare/docs/init/
Reflect / Refraction
miloyip / light2d
https://github.com/miloyip/light2d
这些效果也可简单的在 Cocos2d-x 和 Creator 中实现:
Voronoi diagrams / 维诺图
Fast Voronoi Diagrams and Distance Field Textures on the GPU With the Jump Flooding Algorithm
https://blog.demofox.org/2016/02/29/fast-voronoi-diagrams-and-distance-dield-textures-on-the-gpu-with-the-jump-flooding-algorithm/
JumpFloodAlgorithm 生成 Voronoi 和距离场贴图
https://zhuanlan.zhihu.com/p/222901923
Misc / 杂项
Better Creator / 更好的 Creator 支持
Better Camera / 更好的相机
Camera 摄像机
https://docs.cocos.com/creator/manual/zh/render/camera.html?h=camera
3D Support / 3D 支持
Byte56 GameDev - A light post
http://www.byte56.com/2011/06/a-light-post.html
Voxel Cone Trace / 基于体素锥形光线追踪
关于 VCT（voxel cone trace——基于体素的锥形光线追踪）Renderer 的代码解读
https://blog.csdn.net/xiewenzhao123/article/details/79875855
Voxel Cone Tracing based Global Illumination
https://blog.csdn.net/bugrunner/article/details/8962535
More Refactor / 重构
Gizmo Support / 编辑器可视化支持
TileMap Demo
在我看来，截至到现在，这个项目的 80% 精力都是放在了算法的优化在优化上，剩下的 20%精力则是在渲染上。项目陆陆续续已经做了很久，但是还有很多很多想做的。随便写几个:
已有通用算法的优化 定制型算法，针对一些特定使用场景的算法 纯 GPU算法，半CPU半GPU算法算法已经做了很多，要的数据也到手了，那当然在渲染上要花大力气优化，做出酷炫的效果了 更多的就写在文末的 后续计划 里了 ......
项目是从 Cocos2d-x 开始的，目前几乎所有功能都已经移植了 Creator v1, v2版本。而且所有版本都做了 Native Binding。
但是因为精力有限，后面的新功能打算暂时只对应 Cocos2d-x 和 Creator v2，当然 Creator v3 出来的话也会考虑。暂时只对应Web 版，当然原生也是可以直接用的，Native Binding 暂时不会去对应新功能。
最后打个广告，最近上架了一款关于 FBO 的插件扩展，后续也会用到 GPU阴影算法的实现中，有兴趣的朋友也可以支持一下。
cc.RenderTexture cc.Camera FBO截图/放大镜/Shader 伴侣：
https://forum.cocos.org/t/cc-rendertexture-cc-camera-fbo-shader/99659
以上是由 Cocos 开发者 SuperSuRaccoon 分享的优质技术教程，此文同时参加了 Cocos 中文社区征稿活动，入选优秀稿件。欢迎各位开发者点击【阅读原文】查看原文，为作者点赞，与作者进行交流学习！